﻿namespace Algo.Sort
{
    using System.Collections.Generic;

    internal sealed class MergeSortStrategy : ISortStrategy
    {
        public IEnumerable<T> Sort<T>(IEnumerable<T> items, IComparer<T> comparer, IAlgoExtensions extensions)
        {
            var list = SortUtilities.CopyToList(items);
            if (list.Count <= 1)
            {
                return list;
            }

            var result = new T[list.Count];
            return Sort(0, result.Length - 1, list, result, comparer, extensions);
        }

        private static IList<T> Sort<T>(int left, int right, IList<T> up, IList<T> down, IComparer<T> comparer, IAlgoExtensions extensions)
        {
            if (left == right)
            {
                down[left] = up[left];
                return down;
            }

            var mid = (left + right) / 2;
            var leftArray = Sort(left, mid, up, down, comparer, extensions);
            var rightArray = Sort(mid + 1, right, up, down, comparer, extensions);
            var curLeft = left;
            var curRight = mid + 1;
            var hasLeftItem = true;
            var hasRightItem = true;
            var iterationsCount = 0;

            var target = ReferenceEquals(leftArray, up) ? down : up;
            for (var i = left; i <= right; i++)
            {
                hasLeftItem = hasLeftItem && curLeft <= mid;
                hasRightItem = hasRightItem && curRight <= right;
                if (hasLeftItem && hasRightItem)
                {
                    var leftItem = leftArray[curLeft];
                    var rightItem = rightArray[curRight];
                    if (SortUtilities.IsGreaterThen(comparer, leftItem, rightItem))
                    {
                        target[i] = rightItem;
                        curRight++;
                    }
                    else
                    {
                        target[i] = leftItem;
                        curLeft++;
                    }

                    iterationsCount++;
                    continue;
                }

                if (hasRightItem)
                {
                    target[i] = rightArray[curRight];
                    curRight++;
                    continue;
                }

                if (hasLeftItem)
                {
                    target[i] = leftArray[curLeft];
                    curLeft++;
                }
            }

            IMetricsExtension metricsBehaviour;
            if (extensions.TryGet(out metricsBehaviour))
            {
                metricsBehaviour.RegisterIterations(iterationsCount);
            }

            return target;
        }
    }
}
